public class Solution {
    public static void main(String[] args) {
        Solution test = new Solution();

        // String s = "bbbab";
        // System.out.println(test.longestPalindromeSubseq(s));

        String s = "mbadm";
        System.out.println(test.minInsertions(s));
    }

    public int longestPalindromeSubseq(String s) {
        /**
         * 最长回文子序列
         * 状态表示：
         *     dp[i][j]表示[i,j]范围内最长回文子序列的长度，为了保证范围有效，故规定i<=j
         * 状态转移方程：
         *      if(s.charAt(i) == s.charAt(j)) {
         *          if(i == j) {
         *              dp[i][j] = 1;
         *          } else if(i+1 == j) {
         *              dp[i][j] = 2;
         *          } else {
         *              dp[i][j] = 2 + dp[i+1][j-1];
         *          }
         *      } else {
         *          dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
         *      }
         * 初始化：
         *      由状态转移方程可知，在填写i，j下标位置元素时，可能会使用到 i+1 j-1位置的元素
         *      仅需使得其填表顺序为从下到上，从左到右即可，并且无需初始化，因为都在装转条件内，不会越界
         * 填表顺序：
         *      从下到上，从左到右
         * 返回值：
         *      return dp[0][n-1];
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        int[][] dp = new int[n][n];
        // 3 初始化

        // 4 填表
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i == j) {
                        dp[i][j] = 1;
                    } else if(i+1 == j) {
                    dp[i][j] = 2;
                    } else {
                        dp[i][j] = 2 + dp[i+1][j-1];
                    }
                } else {
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }
        // 5 返回值
        return dp[0][n-1];
    }

    public int minInsertions(String s) {
        /**
         * 让字符串成为回文串的最少插入次数
         * 状态表示：
         *      dp[i][j]表示让[i,j]范围内字符串成为回文串的最少插入次数
         * 状态转移方程：
         *      if(s.charAt(i) == s.charAt(j)) {
         *          if(i+1 >= j) {
         *              dp[i][j] = 0;
         *          } else {
         *              dp[i][j] = dp[i+1][j-1];
         *          }
         *      } else {
         *          if(i+1 == j) {
         *              dp[i][j] = 1;
         *          } else if(i+1 < j) {
         *              dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
         *          }
         *      }
         * 初始化：
         *      由状态转移方程可得，在对i j位置进行填表时，会使用到i+1 j-1等位置
         *      不过由于状态转移方程中都有处理，因此不会越界访问，故无需初始化
         * 填表顺序：
         *      从下到上，从左到右
         * 返回值：
         *      return dp[0][n-1];
         * */
        // 1 预处理
        int n = s.length();
        // 2 创建dp表
        int[][] dp = new int[n][n];
        // 3 初始化

        // 4 填表
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                    if(i+1 >= j) {
                        dp[i][j] = 0;
                    } else {
                        dp[i][j] = dp[i+1][j-1];
                    }
                } else {
                    if(i+1 == j) {
                        dp[i][j] = 1;
                    } else if(i+1 < j) {
                        dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
                    }
                }
            }
        }
        // 5 返回值
        return dp[0][n-1];
    }
}
